package cn.z2huo.algorithm.dynamicprogramming.matrix;

import java.util.Scanner;

public class Main {
	public void resolve() {
		int number = 0;		//河边的游艇租赁站数目
		int cost = 0;		//花费
		int[][] costArray;
		
		Scanner sc = new Scanner(System.in);
		// 初始化矩阵
		System.out.println("请输入河边的游艇租赁站的数目：");
		number = sc.nextInt();
		costArray = new int[number][number];
		// 给矩阵中的每一个元素进行赋值，元素是各个站点之间的花费
		for(int i=0; i<number-1; i++) {
			for(int j=i+1; j<number; j++) {
				System.out.println("请输入第"+(i+1)+"站到第"+(j+1)+"站所花费租赁费用");
				cost = sc.nextInt();
				costArray[i][j] = cost;
			}
		}
		printArray(costArray);
		sc.close();
		
		// 判断租赁游艇所要花费的最小的费用
		for(int k=2; k<number; k++) {
			for(int i=0; i<number-k; i++) {
				int demo = k+i;
				for(int j=i+1; j<demo; j++) {
					if(costArray[i][j]+costArray[j][demo] < costArray[i][demo]) {
						costArray[i][demo] = costArray[i][j]+costArray[j][demo];
					}
				}
			}
		}
		System.out.println("租赁游艇所花费的最小的费用为："+costArray[0][number-1]);
	}
	//该方法用来输出矩阵
	public void printArray(int[][] array) {
		System.out.println("以下为矩阵的输出");
		for(int i=0; i<array.length; i++) {
			for(int j=0; j<array.length; j++) {
				System.out.printf(" "+array[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Main main = new Main();
		main.resolve();
	}
}
